This invention relates to communication systems; and more particularly, it relates to methods and apparatus for decoding multiple bit sequences that are transmitted simultaneously and asynchronously to a receiving station over a single channel in which the bit sequences are added.
Conventionally, when multiple bit sequences are transmitted at the same time to a receiver, each of the bit sequences is transmitted on a separate channel. In that case, the bit sequences of the separate channels do not interfere with each other. Thus the receiving station can simply filter the signals that are in one channel from the signals that are in the other channels. However, such a system has an inherent deficiency in that it requires multiple communication channels, which in certain instances are not available.
By comparison, with the present invention, multiple bit sequences are sent simultaneously to a receiver over a single channel. In this channel, the bit sequences are added together and thereby form a composite signal which is what the receiver sees. Thus, it is the task of the receiver to decode or recover the bit sequences from which the composite signal was formed.
This decoding problem is addressed in a prior art paper entitled "Minimum Probability of Error for Asynchronous Gaussian Multiple Access Channels" by S. Verdu, IEEE Transactions on Information Theory, IT-32, pp. 85-96, January 1986. In that paper, a decoding procedure is presented which uses a bank of K matched filters (where K is the number of bit sequences that are simultaneously transmitted in the composite signal), followed by a metric evaluation process. However, the Verdu procedure requires a total of 2.sup.K metric calculations for each bit in the composite signal that is decoded; and such exponential dependence on the number of bit sequences in the composite signal makes the Verdu decoder too complex to implement, even for a moderate number of users.
Accordingly, a primary object of the present invention is to provide another decoding procedure, as well as circuitry for carrying out that procedure, which is only linearly dependent on the number of bit sequences that are in the composite signal.